package medium;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 503. 下一个更大元素 II
 * 创建时间：2024/6/24 上午9:19
 * 标签：栈 单调栈
 */
public class 下一个更大元素II_503 {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> deque = new LinkedList<>();
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < 2 * n - 1; i++) {
            while (!deque.isEmpty() &&  nums[deque.peek()] < nums[i % n]) {
                ans[deque.pop()] = nums[i % n];
            }
            deque.push(i % n);
        }
        return ans;
    }
}
